import sun.reflect.generics.tree.Tree;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:翻转二叉树、最近公共祖先
 * Date: 2024-02-05
 * Time:21:45
 */
public class Solution {
    //迭代
/*
    public TreeNode invertTree(TreeNode root) {
        if(root == null)
            return null;
        invertTree(root.left);
        invertTree(root.right);
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        return root;
    }
*/

    //递归
    Stack<TreeNode> stack = new Stack<>();
    public TreeNode invertTree(TreeNode root) {
        if(root == null)
            return null;
        stack.push(root);
        TreeNode node = root;
        while(!stack.isEmpty()) {
            node = stack.pop();
            if(node.right != null) {
                stack.push(node.right);
            }
            if(node.left != null) {
                stack.push(node.left);
            }
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;

        }
        return root;


    }

/////////////////////////////////////////////////


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
/*
        if(root == null)
            return null;
        if(root == p)
            return p;
        if(root == q)
            return q;

        //遍历左、右子树找q、p
        TreeNode ret1 = lowestCommonAncestor(root.left,p,q);
        TreeNode ret2 = lowestCommonAncestor(root.right,p,q);

*/
/*
        if(ret1 == null && ret2 != null)
            return ret2;
        else if(ret1 != null && ret2 == null)
            return ret1;
        else
            return root;
*//*

        if(ret1 != null && ret2 != null) {
            return root;
        } else if(ret1 == null && ret2 != null) {
            return ret2;
        } else if(ret1 != null && ret2 == null) {
            return ret1;
        } else {
            return null;
        }
*/
        TreeNode cur = root;
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();

        getPath(cur,q,stack1);
        getPath(cur,p,stack2);

        int sizeQ = stack1.size();
        int sizeP = stack2.size();
        if(sizeQ > sizeP) {
            int size = sizeQ - sizeP;
            while(size-- > 0) {
                stack1.pop();
            }
        }
        if(sizeQ < sizeP) {
            int size = sizeP - sizeQ;
            while(size-- > 0) {
                stack2.pop();
            }
        }

        while(!stack1.isEmpty()) {
            TreeNode pop1 = stack1.pop();
            TreeNode pop2 = stack2.pop();
            if(pop1.val == pop2.val) {
                return pop1;
            }
        }
        return root;


    }

    //判断某条路径上有没有想找的节点
    private boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack) {
        if(root == null)
            return false;
        stack.push(root);
        if(root.val == node.val)
            return true;


        boolean ret1 = getPath(root.left,node,stack);
        if(!ret1) {
            //左边找不到就去找右边
            boolean ret2 = getPath(root.right,node,stack);
            if(!ret2) {
                stack.pop();
                return false;
            }
        }
        return true;
    }

}
